import collections
from typing import List

class node:
    def __init__(self) -> None:
        self.endWord = None
        self.fail = None
        self.nexts = {}

class AC_Automation:
    def __init__(self):
        self.__root = node()

    def insert(self, word: str) :
        ''' 正常的前缀树插入 '''
        cur = self.__root
        for path in word:
            if path not in cur.nexts:
                cur.nexts[path] = node()
            cur = cur.nexts[path]
        cur.endWord = word

    def build(self):
        ''' 
        构建AC 自动机, fail指针设置 
        BFS构建
         1) 头指向 null
         2) 头子 指向 root
         3)  1' 当前节点，顺着fail 指针找， 如果路上某个节点有当前字符， 指向指向他。
             2' 没有的情况指向根结点
        '''
        q = collections.deque()
        q.append(self.__root)
        while q:
            parent = q.popleft()
            for path, cur in parent.nexts.items():
                cFail = parent.fail
                cur.fail = self.__root
                while cFail:
                    if path in cFail.nexts:
                        cur.fail = cFail.nexts[path]
                        break
                    cFail = cFail.fail
                q.append(cur)

    def containNum(self, content: str) -> int:
        ''' 大文章, 返回有多少个敏感词 '''
        cur = self.__root
        ans = 0
        for path in content:
            while path not in cur.nexts and cur != self.__root:
                cur = cur.fail
            # 来到一个地方
            if path in cur.nexts:
                cur = cur.nexts[path]
            else:
                cur = self.__root
            follow = cur
            while follow != self.__root:
                ans += 1 if follow.endWord != None else 0
                follow = follow.fail
        return ans

    def containWord(self, content: str) -> List[str]:
        ''' 大文章, 包含哪些敏感词 '''
        cur = self.__root
        ans = []
        for path in content:
            while path not in cur.nexts and cur != self.__root:
                cur = cur.fail
            # 来到一个地方
            if path in cur.nexts:
                cur = cur.nexts[path]
            else:
                cur = self.__root
            follow = cur
            while follow != self.__root:
                if follow.endWord:
                    ans.append(follow.endWord)
                follow = follow.fail
        return ans


if __name__ == '__main__':
    ac = AC_Automation()
    ac.insert("你好")
    ac.insert("彩笔")
    ac.insert("垃圾")
    ac.insert("丢")
    ac.insert("一")
    ac.build()

    content = '你好啊, 我我哦nihao 你好我, 我是你菜a彩笔, 有个垃圾, 应该扔掉, 一二三'
    print(ac.containNum(content))
    print(ac.containWord(content))